/**
 * 希尔排序
 * 假设数组长度：n
 * 第一次分组：分成n/2组，下标0和n/2为一组，1和n/2+1为一组，2和n/2+2为一组，……；组内插入排序
 * 第二次分组：分成n/2/2组，下标0和n/2/2为一组，……；组内插入排序
 * ……
 * 最后一次分组：分成一组；组内插入排序
 */
public class ShellSort {

    //升序
    public void sort(int[] nums){
        int n = nums.length;
        //gap为下标的增量：n/2,n/2/2,n/2/2/2,……,1
        int currentValue,gap = n/2;
        while (gap>0){
            //组内插入排序
            for (int i = gap; i < n; i++) {
                currentValue = nums[i];
                //当前是i,前面排好序的下标为：i-gap,i-gap-gap,……
                int preIndex = i - gap;
                /**
                 * 这层while循环就是将已经排序好的比currentValue大的都后移动一位
                 */
                while (preIndex>=0&&nums[preIndex]>currentValue){
                    nums[preIndex+gap] = nums[preIndex];
                    preIndex -= gap;
                }
                //插入
                nums[preIndex+gap] = currentValue;
            }
            //
            gap = gap/2;
        }
    }

    public static void main(String[] args) {
        int[] nums = {12,10,9,-13,7,19,76};
        ShellSort shellSort = new ShellSort();
        shellSort.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
